package com.fengdi.book.easy.String;

import java.util.ArrayList;

public class StrStr {
    public int strStr(String haystack, String needle) {
        int max = haystack.length() - needle.length();

        char begin = needle.charAt(0);
        // 记录开始元素与needle相同的下标
        ArrayList<Integer> indexList = new ArrayList<>();

        for(int i = 0; i <= max; i++) {
            if(haystack.charAt(i) == begin) {
                indexList.add(i);
            }
        }

        for(int i = 0; i < indexList.size(); i++) {
            int index = indexList.get(i);
            int j = 0;
            for(; j < needle.length(); j++) {
                if(haystack.charAt(index + j) != needle.charAt(j)) {
                    break;
                }
            }
            if(j == needle.length()) {
                return index;
            }
        }

        return -1;
    }
}
